package com.mashibing.class14;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 贪心算法的解题套路实战
 *输入: 正数数组costs、正数数组profits、正数K、正数M
 * costs[i]表示i号项目的花费
 * profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
 * K表示你只能串行的最多做k个项目
 * M表示你初始的资金
 * 说明: 每做完一个项目，马上获得的收益，可以支持你去做下一个项目。不能并行的做项目。
 * 输出：你最后获得的最大钱数。
 */
public class Code04_IPO {
    // 最多K个项目
    // W是初始资金
    // Profits[] Capital[] 一定等长
    // 返回最终最大的资金
    public static int findMaximizedCapital(int K, int W, int[] Profits, int[] Capital) {
        // 花费堆, 小根堆, 谁花费小, 谁在小根堆堆顶.
        PriorityQueue<Program> minCostQ = new PriorityQueue<>(new MinCostComparator());
        // 利润堆, 大根堆, 谁利润大, 谁就在大根堆堆顶
        PriorityQueue<Program> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
        // 建立出所有项目 将其项目插入花费堆(小根堆)中.
        for (int i = 0; i < Profits.length; i++) {
            minCostQ.add(new Program(Profits[i], Capital[i]));
        }
        // 第0轮  第1轮 ..... 第K-1轮
        for (int i = 0; i < K; i++) {
            // 小根堆不为空, 并且小根堆中的堆顶元素的花费小于或者等于W 弹出花费堆(小根堆)的堆顶元素加入利润堆(大根堆)中.
            while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
                maxProfitQ.add(minCostQ.poll());
            }
            if (maxProfitQ.isEmpty()) { // 经历过解锁之后, 利润堆(大根堆)中没有元素, 直接提前结束.
                return W;
            }
            W += maxProfitQ.poll().p; // 弹出利润堆(大根堆)中的一个项目, 取出该项目的利润 累加到W中.
        }
        return W;
    }

    public static class Program {
        public int p; // 利润资金 -- 回报.
        public int c; // 花费资金 -- 投资

        public Program(int p, int c) {
            this.p = p;
            this.c = c;
        }
    }

    public static class MinCostComparator implements Comparator<Program> {

        @Override
        public int compare(Program o1, Program o2) {
            return o1.c - o2.c; // 花费比较器, 谁花费小 谁放在前面
        }
    }

    public static class MaxProfitComparator implements Comparator<Program> {

        @Override
        public int compare(Program o1, Program o2) {
            return o2.p - o1.p;// 利润比较器, 谁利润大 谁放在前面.
        }
    }

}
